package com.cty.tenthDay;

import java.util.Arrays;

/*
*
* 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
* 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
* */
public class Q_12 {
    public static void main(String[] args) {
        String s = "abc";
        String t = "ac";
        String s1 = minWindow2(s, t);
        System.out.println(s1);
    }

    //这道题主包不会 看官方的力扣题解 diff++ 的思路
    public static String minWindow(String s, String t) {
        int sLen = s.length(),tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) return "";
        // 用来记录s的字符数组
        char[] sCharArr = s.toCharArray();
        // 记录窗口中的字符种类与数量
        int[] winCharNums = new int[128];
        //将t中的字符数量计算下来
        int[] tCharNums = new int[128];
        // 记录t中的字符数量与种类
        for (char c : t.toCharArray()) {
            tCharNums[c]++;
        }
        //滑动窗口的有边界
        int right = 0;
        // 活动窗口的左边界
        int left = 0;
        // 两个字母表的种类的差距
        int diff = 0;
        // 记录最小字串的开始索引
        int begin = 0;
        // 记录字串的最小长度
        int minLen = sLen + 1;
        while (right < sLen) {
            // 先判断t中是否有这个字符
            if (tCharNums[sCharArr[right]] == 0) {
                right++;
                continue;
            }
            // 判断窗口中的字母的数量是否相遇t中字母的数量
            if (winCharNums[sCharArr[right]] < tCharNums[sCharArr[right]]) {
                diff++;
            }
            // 让窗口中字母的数量加一
            winCharNums[sCharArr[right]]++;
            // 右边界右移
            right++;
            // 当diff与tLen相同时 表示窗口中的字母数量满足了t字符串中的字母数量
            while (diff == tLen) {
                // 判断字串的最小长度是否合格
                if (minLen > right - left) {
                    begin = left;
                    minLen = right - left;
                }
                // 如果最左边的元素 在t中不存在 直接跳过
                if (tCharNums[sCharArr[left]] == 0) {
                    left++;
                    continue;
                }

                // 当滑动窗口中字母的数量与t中的数量相等时 diff--
                if (winCharNums[sCharArr[left]] == tCharNums[sCharArr[left]]) {
                    diff--;
                }
                // 滑动窗口中的数量减小
                winCharNums[sCharArr[left]]--;
                // 左边界右移
                left++;
            }
        }
        // 如果最小长度没有变 则不含有最小子串
        if (minLen == sLen + 1) {
            return "";
        }
        // 返回最小子串
        return s.substring(begin,begin + minLen);
    }

    // diff--的思路
    public static String minWindow2(String s, String t) {
        int sLen = s.length(),tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) return "";
        char[] sCharArr = s.toCharArray();
        int[] tCharNums = new int[128];
        for (char c : t.toCharArray()) {
            tCharNums[c]++;
        }
        //滑动窗口的有边界
        int right = 0;
        // 活动窗口的左边界
        int left = 0;
        // 两个字母表的种类的差距
        int diff = tLen;
        // 记录最小字串的开始索引
        int begin = 0;
        // 记录字串的最小长度
        int minLen = sLen + 1;
        while (right < sLen) {
            if (tCharNums[sCharArr[right]] > 0) {
                diff--;
            }
            tCharNums[sCharArr[right]]--;
            right++;

            while (diff == 0) {
                if (minLen > right - left) {
                    begin = left;
                    minLen = right - left;
                }

                if (tCharNums[sCharArr[left]] == 0) {
                    diff++;
                }
                tCharNums[sCharArr[left]]++;
                left++;
            }
        }
        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin,begin + minLen);
    }

}
